package arithmetic.LeetCode;
import groovy.json.JsonOutput;
import java.util.Arrays;
import java.util.Scanner;
import java.util.concurrent.Executor;
import java.util.concurrent.Executors;

/**
 * 牛客网 模板 购物单
 * https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tqId=21239&rp=0&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking&tPage=1
 */
public class Main {
    class Item{
        int value;
        int point;
        int q;
    }
    public static void main(String[] args) {
       /* Scanner scanner= new Scanner(System.in);
         while(scanner.hasNext()){
            String s = scanner.nextLine();
            String[] ss = s.split(" ");
            int price = Integer.valueOf(ss[0]);
            int size = Integer.valueOf(ss[1]);

            int i=1;
            int[] v = new int[size+1];
            int[] p = new int[size+1];
            int[] q = new int[size+1];
            while (i<=size){
                s = scanner.nextLine();
                ss = s.split(" ");
                v[i]=Integer.valueOf(ss[0]);//价格
                p[i]=Integer.valueOf(ss[1])*v[i];//重要度*价格
                q[i]=Integer.valueOf(ss[2]);//价格
                i++;
            }

            bagSolution(v,p,q,price);
         }*/

       /* 1738 55
        20 3 0
        50 2 0
        120 3 0
        40 3 0
        100 4 0
        220 2 0
        40 2 0
        200 3 0
        90 3 0
        10 3 0
        230 2 0
        300 1 0
        70 2 0
        270 1 0
        300 3 0
        70 5 0
        300 2 0
        200 1 0
        210 1 0
        270 2 0
        180 2 0
        40 2 0
        110 4 0
        170 4 0
        110 1 0
        280 4 0
        50 4 0
        160 2 0
        10 3 0
        320 3 0
        10 5 0
        50 2 0
        230 4 0
        230 1 0
        150 5 0
        160 5 0
        90 5 0
        140 3 0
        140 3 0
        250 5 0
        330 2 0
        190 3 0
        230 1 0
        70 2 0
        50 3 0
        170 5 0
        100 5 0
        230 5 0
        120 1 0
        70 2 0
        50 3 0
        240 1 0
        220 1 0
        20 5 0
        20 3 0*/

       int[] v = {0,800,400,300,400,500};
       int[] p = {0,1600,2000,1500,1200,1000};
       int[] q = {0,0,1,1,0,0};
       int price=1000;

        bagSolution(v,p,q,price);

        //Arrays.sort();
        Executors.newCachedThreadPool();

    }

    /**
     * 链接：https://www.nowcoder.com/questionTerminal/f9c6f980eeec43ef85be20755ddbeaf4?f=discussion
     * 来源：牛客网
     *
     * 初始值java默认赋值为0,其中dp[0][0...sum_money]为0,从dp[1][0...sum_money]
     *   计算第1行,代表第一件物品
     * dp[i][sum_money] ： 前i个物体放入容量为sum_money的背包的最大价值；
     * dp[i-1][sum_money] ： 前i-1个物体放入容量为sum_money的背包的最大价值；
     * dp[i-1][sum_money-price[i]] ： 前i-1个物体放入容量为sum_money-price[i]的背包的最大价值；
     * dp[i][sum_money]=Math.max{dp[i-1][sum_money-price[i]]+val[i] , dp[i-1][sum_money]}
     *
     * @param price
     */
    private static void bagSolution(int[] v,int[] p,int[] q, int price) {
        int[][] dp = new int[v.length+1][];//物品总数和钱数
        dp[0]=new int[price+1];
        for (int i = 1; i <v.length ; i++) {
            dp[i]=new int[price+1];
            // 成本
            for (int j = 0; j <= price; j++) {
                dp[i][j]=dp[i-1][j]; // 默认值是上一个物品的最优值
                if(q[i]==0){//主件
                    if (j >= v[i]) {
                        dp[i][j] = Math.max(dp[i - 1][j-v[i]] + p[i],dp[i-1][j]);
                    }

                }else {// 附件 ,必须买主件
                    if (j >= v[i] + v[q[i]]) {
                        dp[i][j] = Math.max(dp[i - 1][j - v[i] - v[q[i]]] + p[i] + p[q[i]], dp[i - 1][j]);
                    }
                }
            }
        }
        System.out.println(dp[v.length-1][price]);
        System.out.println(JsonOutput.toJson(dp));

    }

    /**
     * 打印字符串,8个一行,少于8个则换行
     * @param s
     */
    public static void printString(String s){
        if(s.length()<1){return;}
        int  index =0;
        String a="0000000";
        while(index<s.length()){
            if(index+8<s.length()){
                System.out.println(s.substring(index,index+8));
            }else{
                System.out.println(s.substring(index)+a.substring(7-(index+8-s.length())));
            }
            index+=8;
        }
    }

}